package com.leetcode.binarytree;

import com.leetcode.datastructure.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2019/11/6
 * @description: 113. 路径总和 II
 * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
 * 说明: 叶子节点是指没有子节点的节点。
 */
public class PathSumII113B {

	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		List<List<Integer>> result = new ArrayList<>();
		if (root == null) {
			return result;
		}
		///1.获取所有的叶子路径集合
		List<Integer> first = new ArrayList<>();
		first.add(root.val);
		///单个元素判断
		if (root.left==null&&root.right==null){
			if(root.val==sum){
				result.add(first);
			}
		}
		if (root.left != null) {
			List<Integer> tempLeft = new ArrayList<>(first);
			getPathList(root.left, result, tempLeft, sum);
		}
		if (root.right != null) {
			List<Integer> tempRight = new ArrayList<>(first);
			getPathList(root.right, result, tempRight, sum);
		}

		return result;
	}

	/**
	 * @param node 当前节点
	 * @param res  返回结果
	 */
	private void getPathList(TreeNode node, List<List<Integer>> res, List<Integer> path, int sum) {
		path.add(node.val);
		///到叶子节点
		if (node.left == null && node.right == null) {
			///判断和是否满足
			int temp = 0;
			for (Integer item :
					path) {
				temp+=item;
			}
			if (sum==temp){
				res.add(path);
			}

			return;
		}

		if (node.left != null) {
			List<Integer> tempLeft = new ArrayList<>(path);
			getPathList(node.left, res, tempLeft, sum);
		}
		if (node.right != null) {
			List<Integer> tempRight = new ArrayList<>(path);
			getPathList(node.right, res, tempRight, sum);
		}
	}


	@Test
	public void test() {
		int i = 1;
		Integer in = new Integer(1);
		System.out.println(i == in);

	}

	@Test
	public void testPathSum() {
		TreeNode node = TreeNode.stringToTreeNode("[5,4,8,11,null,13,4,7,2,null,null,5,1]");
		System.out.println(pathSum(node, 22));
	}
}
